Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/unix/volume14/bsd-dyna-link

Internet Message Format | 1988-05-08 | 57.7 KB

Subject:  v14i089:  Dynamic linking package for BSD
Newsgroups: comp.sources.unix
Sender: sources
Approved: [e-mail]

Submitted-by: Dave Jones <megatest!djones>
Posting-number: Volume 14, Issue 89
Archive-name: bsd-dyna-link

[  I thought about asking for a Makefile and manpage, and probably made
   a mistake in not asking for it.  --r$  ]

I made a casual mention of a dynamic linking routine a while back, and
I was overwhelmed with requests for it.  My software manager has kindly
said, okay, let'er rip.

DISCLAIMER:
As is usual with free software, neither I nor my employeer assumes any
responsibility at all for these routines.  I hope they work good and
last a long time, but if they don't, don't come whining to me.
And please do not install them as part of anything that shoots.

The following routines are for doing dynamic loading under SunOS-3.
You can probably hack it up pretty easily to run under any BSD-related
system.  I don't know off-hand how much the System V a.out format
and the COFF format are like BSD's a.out.  You might have some trouble
porting it to one of those.

Good luck.

And oh, yes.  Please don't call me for support (unless you have something
really fabulous to trade).

        Dave Jones
        Megatest Corp.
        880 Fox Lane
        San Jose, CA.
        95131

        [phone] Ext 3227
        UUCP: ucbvax!sun!megatest!djones
        ARPA: megatest![e-mail]

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of shell archive."
# Contents:  dyna_link.c dyna_link.doc dyna_link.h assoc.c assoc.doc
#   assoc_internals.h assoc.h which.c smalloc.c argv.c
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f dyna_link.c -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"dyna_link.c\"
else
echo shar: Extracting \"dyna_link.c\" \(14909 characters\)
sed "s/^X//" >dyna_link.c <<'END_OF_dyna_link.c'
X/*
X**   #include <a.out.h>
X**   #include "assoc.h"
X**   #include "dyna_link.h
X**
X**
X**   lk_get_header(fd, hdrp, offset)  /@ reads an a.out header into memory @/
X**      int fd;               /@ an open file-descriptor @/
X**      struct exec *hdrp;    /@ pointer to memory for a.out header @/
X**      long offset;          /@ displacement of file (for archives)@/
X**
X**   lk_get_symbols(fd, hdrp, offset)  /@ Reads symbols into memory @/
X**      int fd;               /@ an open file-descriptor @/
X**      struct exec *hdrp;    /@ pointer to previously initialized header @/
X**      long offset;          /@ displacement of file (for archives) @/
X**
X**   assoc_mem
X**   lk_sym_hash(hdrp, syms); /@ Creates lookup-table for symbols @/
X**      struct exec *hdrp;    /@ pointer to previously initialized header @/
X**      struct nlist *syms;   /@ pointer to previously initialized symbols @/
X**
X**   func_ptr
X**   lk_dynaload(codep, hdrp, hash_table, filename) /@ loads named file @/
X**      int* codep;           /@ pointer to memory for return-code @/
X**      struct exec* hdrp;    /@ pointer to previously initialized header @/
X**      assoc_mem hash_table; /@ previously initialized lookup-table @/
X**      char* filename;
X**
X**   func_ptr  /@ loads a file, given by file-descriptor and offset. @/
X**   lk_dynaload_fd(codep, hdrp, hash_tab, fd, offset)
X**     int *codep;            /@ pointer to memory for return-code @/
X**     struct exec *hdrp;     /@ pointer to previously initialized header @/
X**     assoc_mem hash_tab;    /@ previously initialized lookup-table @/
X**     int fd;                /@ an open file-descriptor @/
X**     long disp;             /@ displacement of file (for archives) @/
X**
X**   This library furnishes routines for doing a dynamic load of an executable
X**   segment ( .o file).
X**
X**   The caller first must build a lookup-table for the symbols
X**   of the executing program.  (See assoc.doc for description
X**   of lookup-table routines.)
X**
X**   Once the lookup-table has been made, the program may repeatedly call
X**   lk_dynaload() or lk_dynaload_fd() to load segments.
X**   Loaded segments may be freed using free().
X**
X**   The routines to be used for building the lookup-table are
X**   lk_get_header(), lk_get_symbols(), and lk_sym_hash().  These are
X**   also potentially useful for other link-editor applications, and
X**   for that reason are parameterized so that they may be used on
X**   archive members, as well as on individual a.out files.
X**
X**   lk_get_header() returns 0 on success, -1 on failure.  Sets errno.
X**
X**   lk_get_symbols() returns a buffer from malloc() on success, null
X**     on failure.  Sets errno.
X**
X**   lk_sym_hash() returns an assoc_mem on success (see assoc.doc), null
X**     on failure.  Sets errno.
X**
X**   lk_dynaload() and lk_dynaload_fd() return a pointer to the entry-point
X**     of the .o file on success, null on failure.  Sets *codep (see
X**     parameters).  The values for *codep are defined in dyna_link.h:
X**
X**      #define lk_ok 0
X**      #define lk_undefd 1
X**      #define lk_bad_format 2
X**      #define lk_perror -1
X**
X**   lk_ok means "okay."
X**   lk_undefd means that one or more symbols required by the .o file
X**     are not defined in the lookup-table.  In this case the char**
X**     lk_undefined will have been set to point to a vector containing
X**     the undefined symbols.
X**   lk_bad_format means that the .o file is not formatted occording
X**     to the a.out file conventions.
X**   lk_perror means that errno has been set.
X**
X**
X**   Tutorial example:
X**
X**   main(argc, argv)
X**     char** argv;
X**   {
X**     char* me = (char*) which(argv[0]);
X**     char* prog = (char*)(argv[1]);
X**     func_ptr entry_point;
X**     assoc_mem hash_tab;
X**     struct exec main_hdr;
X**     struct nlist * main_syms;
X**     int code;
X**     int fd = open( me, O_RDONLY );
X**
X**     lk_get_header(fd, &main_hdr, 0 );
X**     main_syms = lk_get_symbols(fd, &main_hdr, 0 );
X**     close(fd);
X**     hash_tab = lk_sym_hash(&main_hdr, main_syms);
X**
X**     (func_ptr) entry_point
X**                 = lk_dynaload( &code, &main_hdr, hash_tab, prog );
X**     if(entry_point)
X**           (*(func_ptr) entry_point)();
X**     else
X**        switch(code)
X**           {
X**           case lk_undefd:
X**             { char** undef = lk_undefined;
X**           printf("undefined:\n");
X**           while(*undef) printf("%s\n", *undef++);
X**             }
X**             break;
X**           case lk_perror:
X**             perror(prog);
X**             break;
X**           case lk_bad_format:
X**             printf("bad format\n");
X**             break;
X**           }
X**         }
X**     }
X**     exit(0);
X**   }
X**
X*/
X
X
X#include <stdio.h>
X#include <a.out.h>
X#include <sys/file.h>
X#include <sys/types.h>
X#include <errno.h>
X#include <sys/stat.h>
X#include <ctype.h>
X
X#include "assoc.h"
X#include "dyna_link.h"
X
Xlk_get_header(fd, hdrp, disp)
X  int fd;
X  struct exec *hdrp;
X  long disp;
X{
X  lseek(fd, disp, 0);
X  if (read(fd, hdrp, sizeof(struct exec)) != sizeof(struct exec))
X    {hdrp->a_magic = 0;  return -1; }
X  return 0;
X}
X
X/* This routine buffers up the symbols and strings from a file. */
X/* Converts file-displacements of strings to pointers.          */
Xstruct nlist *
Xlk_get_symbols(fd, hdrp, disp)
X  int fd;
X  struct exec *hdrp;
X  long disp;
X{
X  struct nlist * buffer;
X  unsigned long size;
X
X  if(N_BADMAG(*hdrp))
X    { errno = ENOEXEC;
X      return 0;
X    }
X
X  lseek(fd, disp + N_SYMOFF(*hdrp) + hdrp->a_syms, 0);
X  if(read(fd, &size, 4) != 4)
X    return 0;
X
X  buffer = (struct nlist*) malloc(hdrp->a_syms + size);
X  if(buffer == 0) return 0;
X
X  lseek(fd, disp + N_SYMOFF(*hdrp), 0);
X  if(read(fd, buffer, hdrp->a_syms + size) != hdrp->a_syms + size)
X    { free(buffer);
X      return 0;
X    }
X
X  {
X    struct nlist * sym = buffer;
X    struct nlist * end = sym + hdrp->a_syms / sizeof(struct nlist);
X    long displ = (long)buffer + (long)(hdrp->a_syms);
X
X    while(sym < end)
X      {
X    sym->n_un.n_name = (char*)sym->n_un.n_strx + displ;
X    sym++;
X      }
X  }
X  return buffer;
X
X}
Xstatic file_size;
X
X/* Buffers up relocation info */
Xstruct relocation_info *
Xlk_get_reloc(fd, hdrp, disp)
X     int fd;
X     struct exec *hdrp;
X     long disp;
X{
X  struct relocation_info * buffer;
X  int size;
X
X
X  if(N_BADMAG(*hdrp))
X    { errno = ENOEXEC;
X      return 0;
X    }
X
X  lseek(fd, disp + N_TXTOFF(*hdrp) + hdrp->a_text + hdrp->a_data, 0);
X
X  size = hdrp->a_trsize + hdrp->a_drsize;
X  buffer = (struct relocation_info*) malloc( size );
X
X  if(buffer == 0) return 0;
X
X  if(read(fd, buffer, size) !=  size)
X    { free(buffer);
X      return 0;
X    }
X
X  return buffer;
X
X}
X
X/* Buffers up text and data */
Xstatic
Xunsigned char *
Xlk_get_text_and_data(fd, hdrp, bss, disp )
X  int fd;
X  struct exec *hdrp;
X  int bss; /* -1 iff we should allocate hdrp->a_bss extra space,
X       ** larger numbers indicate extra space to allocate
X       */
X  long disp;
X{
X  unsigned char * buffer;
X  int size;
X
X  if(N_BADMAG(*hdrp))
X    {
X      errno = ENOEXEC;
X      return 0;
X    }
X
X  lseek(fd, disp + N_TXTOFF(*hdrp), 0);
X
X  size = hdrp->a_text + hdrp->a_data;
X
X  if(bss == -1) size += hdrp->a_bss;
X  else if (bss > 1) size += bss;
X
X  buffer = (unsigned char*) malloc( size );
X
X  if(buffer == 0) return 0;
X
X  if(read(fd, buffer, size) !=  size)
X    { free(buffer);
X      return 0;
X    }
X
X  if(bss == -1)
X    bzero(buffer +  hdrp->a_text + hdrp->a_data, hdrp->a_bss);
X  else if(bss > 0)
X    bzero(buffer +  hdrp->a_text + hdrp->a_data, bss );
X
X  return buffer;
X
X}
X
Xchar** lk_undefined = 0;
X
Xfunc_ptr
Xlk_dynaload_fd(codep, hdrp, hash_tab, fd, disp)
X  int *codep;
X  struct exec *hdrp;
X  assoc_mem hash_tab;
X  int fd;
X  long disp;
X{
X  func_ptr retval = 0;
X  unsigned char* text_data_bss;
X  struct exec header;
X  struct nlist * symbols = 0;
X  struct relocation_info * reloc = 0;
X  long new_common = 0; /* Length of new common */
X  assoc_mem lk_sym_hash();
X  int undefineds = 0;
X  char*** argv_h = 0;
X
X  *codep = 0;
X
X  if(fd < 0) { *codep = lk_perror; goto end; }
X
X  if(  lk_get_header(fd, &header, 0) != 0
X     ||(reloc = lk_get_reloc(fd, &header, 0)) == 0
X     ||(symbols = lk_get_symbols(fd, &header, 0 )) == 0
X    )
X    { *codep = lk_perror; goto end; }
X
X
X  if(  header.a_magic != 0x107 )
X    { *codep = lk_bad_format; goto end; }
X
X  /* First we will buzz through the new symbols, resolving them.
X  */
X  { struct nlist * symbol = symbols;
X    struct nlist * endp = symbols + (header.a_syms / sizeof(struct nlist));
X    long last_value = new_common;
X    while(symbol < endp)
X      { int type;
X    int value;
X    struct nlist * old_symbol = 0;
X    struct nlist ** old_symbol_p = 0;
X
X    type = symbol->n_type;
X        value = symbol->n_value;
X
X    if(type == N_EXT + N_UNDF )
X      { /* is not defined here yet. */
X          old_symbol_p = (struct nlist **)
X          assoc_lookup(symbol->n_un.n_name, hash_tab);
X
X        if(old_symbol_p) old_symbol = *old_symbol_p;
X
X        if(value != 0)
X          { /* is common */
X        if(old_symbol == 0)
X          { /* is new common */
X            int rnd =
X              value >= sizeof(double) ? sizeof(double) - 1
X            : value >= sizeof(long) ? sizeof(long) - 1
X              : sizeof(short) - 1;
X
X            symbol->n_type = N_COMM;
X            new_common += rnd;
X            new_common &= ~(long)rnd;
X            symbol->n_value = new_common;
X            new_common += value;
X          }
X        else
X          { /* Is old common */
X
X            symbol->n_type = N_EXT + N_COMM;
X            symbol->n_value = old_symbol -> n_value;
X          }
X        last_value = symbol->n_value;
X          } /* end .. is common */
X        else
X          { /* is extern */
X        if(old_symbol == 0)
X          { /* symbol is unresolved. Sigh. */
X            /* But will will keep on going, looking for others. */
X            if(argv_h == 0)
X              argv_h = (char***) argv_new();
X            argv_put(argv_h, symbol->n_un.n_name);
X            undefineds = 1;
X          }
X        else
X          {
X            symbol->n_type = N_EXT + N_COMM;
X            symbol->n_value = old_symbol -> n_value;
X            last_value = symbol->n_value;
X          }
X          }
X      } /* end.. is undefined */
X
X#       ifdef do_stabs
X    if(type&N_EXT && type&N_TYPE == N_UNDF && type&N_STAB)
X      {
X        symbol->n_value = last_value;
X        symbol->n_type = (type&N_STAB) | (N_EXT+N_COMM);
X      }
X#       endif
X    symbol++;
X      }
X  } /* end buzz */
X
X  if(undefineds) { goto end; }
X  retval = (func_ptr)lk_get_text_and_data(fd, &header, header.a_bss + new_common, 0 );
X
X
X  /* Now zip through relocation data, doing our stuff.
X  ** First comes the text-relocation
X  */
X  {
X    struct relocation_info * rel = reloc;
X    struct relocation_info * first_data =
X      reloc +
X    (header.a_trsize  / sizeof(struct relocation_info));
X
X    struct relocation_info * endp =
X      reloc +
X    (header.a_trsize + header.a_drsize )/ sizeof(struct relocation_info);
X
X    while(rel < endp )
X      {
X
X    char *address =
X      (char*) (rel->r_address + (long)retval);
X
X    long datum;
X
X    if(rel >= first_data)
X      address += header.a_text;
X
X    switch (rel->r_length)
X      {
X      case 0:        /* byte */
X        datum = *address;
X        break;
X
X      case 1:        /* word */
X        datum = *(short *)address;
X        break;
X
X      case 2:        /* long */
X        datum = *(long *)address;
X        break;
X
X      default:
X        { *codep = lk_bad_format;
X          goto end;
X        }
X
X      }
X
X    if(rel->r_extern)
X      { /* Look it up in symbol-table */
X        struct nlist * symbol = &(symbols[rel->r_symbolnum]);
X        int type = symbol->n_type;
X        char* name = symbol->n_un.n_name;
X        int value = symbol->n_value;
X
X        if(symbol->n_type == N_EXT + N_COMM)
X          /* old common or external */
X           datum += symbol->n_value;
X        else if (symbol->n_type == N_COMM)
X          /* new common */
X          datum += (long)retval + header.a_text + header.a_data;
X        else {  *codep = lk_bad_format; goto end; }
X      } /* end.. look it up */
X    else
X      { /* is static */
X        switch(rel->r_symbolnum & N_TYPE)
X          {
X          case N_TEXT: case N_DATA:
X        datum += (long)retval;
X        break;
X          case N_BSS:
X        datum += (long)retval +  new_common;
X        break;
X          case N_ABS:
X        break;
X          }
X      } /* end .. is static */
X    if(rel->r_pcrel) datum -= (long)retval;
X
X    switch (rel->r_length) {
X
X    case 0:        /* byte */
X      if (datum < -128 || datum > 127)
X        {
X          *codep = lk_bad_format; goto end;
X        }
X      *address = datum;
X      break;
X    case 1:        /* word */
X      if (datum < -32768 || datum > 32767)
X        {
X          *codep = lk_bad_format; goto end;
X        }
X      *(short *)address = datum;
X      break;
X    case 2:        /* long */
X      *(long *)address = datum;
X      break;
X    }
X    rel++;
X      }
X
X  } /* end.. zip */
X
X end:
X
X  sfree(reloc); sfree(symbols);
X
X  if(*codep != 0) { sfree(retval); retval = 0; }
X  if(undefineds)
X    { *codep = lk_undefd;
X      sfree(lk_undefined);
X      lk_undefined = *argv_h;
X      free(argv_h);
X    }
X  return retval;
X
X}
X
Xfunc_ptr
Xlk_dynaload( codep, hdrp, hash_tab, filename )
X  int *codep;
X  struct exec *hdrp;
X  assoc_mem hash_tab;
X  char* filename;
X{
X
X  int fd = open(filename, O_RDONLY );
X  func_ptr retval = lk_dynaload_fd(codep, hdrp, hash_tab, fd, 0);
X
X  if(fd >= 0) close(fd);
X  return retval;
X
X}
X
Xassoc_mem
Xlk_sym_hash(hdrp, syms)
X  struct exec * hdrp;
X  struct nlist * syms;
X{
X  assoc_mem result = new_assoc_mem(sizeof(struct nlist*));
X
X  if(result == 0) return 0;
X
X  {
X    struct nlist * sym = syms;
X    struct nlist * end = syms + (hdrp->a_syms / sizeof(struct nlist));
X
X    while(sym < end)
X      {
X    struct nlist ** ptr = (struct nlist**) assoc(sym->n_un.n_name, result);
X    if(ptr == 0) return 0;
X    *ptr = sym;
X    sym++;
X      }
X  }
X  return result;
X}
X
X#undef demo_dyna_link
X
X#ifdef demo_dyna_link
Xmain(argc, argv)
X  char** argv;
X{
X  char* me = (char*) which(argv[0]);
X  char* prog = (char*)(argv[1]);
X  func_ptr tion;
X  assoc_mem hash_tab;
X  struct exec main_hdr;
X  struct nlist * main_syms;
X
X  int fd = open( me, O_RDONLY );
X
X  lk_get_header(fd, &main_hdr, 0 );
X  main_syms = lk_get_symbols(fd, &main_hdr, 0 );
X  close(fd);
X  hash_tab = lk_sym_hash(&main_hdr, main_syms);
X
X  { int times;
X    int code;
X
X    if(argc==2) times = 1;
X      else times = atoi(argv[2]);
X
X    while(times--)
X      {
X#       include <sys/time.h>
X    struct timeval t1, t2;
X    struct timezone tz;
X    long usecs;
X    gettimeofday(&t1, &tz);
X    (func_ptr)tion = lk_dynaload( &code, &main_hdr, hash_tab, prog );
X    gettimeofday(&t2, &tz);
X
X    usecs =( t2.tv_sec - t1.tv_sec ) * 1000000 + t2.tv_usec - t1.tv_usec;
X/*    fprintf(stderr, "%d %d %d\n", usecs, t2.tv_sec - t1.tv_sec,
X        t2.tv_usec - t1.tv_usec);
X*/
X    if(tion)
X      (*(func_ptr)tion)();
X    else
X      switch(code)
X        {
X        case lk_undefd:
X          { char** undef = lk_undefined;
X        printf("undefined:\n");
X        while(*undef) printf("%s\n", *undef++);
X          }
X          break;
X        case lk_perror:
X          perror(prog);
X          break;
X        case lk_bad_format:
X          printf("bad format\n");
X          break;
X        }
X      }
X  }
X  exit(0);
X}
X
Xint xstderr;
Xint xfprintf;
X
Xkluge() { printf(); }
X
Xint comm_main;
Xint ext;
Xfoo()
X{
X  fprintf(stderr, "(%x %x)foo be called.\n", stderr, fprintf);
X  fprintf(stderr, "(%x %x) <<\n", xstderr, xfprintf);
X}
X
X#endif demo_dyna_link
END_OF_dyna_link.c
if test 14909 -ne `wc -c <dyna_link.c`; then
    echo shar: \"dyna_link.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f dyna_link.doc -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"dyna_link.doc\"
else
echo shar: Extracting \"dyna_link.doc\" \(4389 characters\)
sed "s/^X//" >dyna_link.doc <<'END_OF_dyna_link.doc'
X   #include <a.out.h>
X   #include "assoc.h"
X   #include "dyna_link.h
X
X
X   lk_get_header(fd, hdrp, offset)  /@ reads an a.out header into memory @/
X      int fd;               /@ an open file-descriptor @/
X      struct exec *hdrp;    /@ pointer to memory for a.out header @/
X      long offset;          /@ displacement of file (for archives)@/
X
X   lk_get_symbols(fd, hdrp, offset)  /@ Reads symbols into memory @/
X      int fd;               /@ an open file-descriptor @/
X      struct exec *hdrp;    /@ pointer to previously initialized header @/
X      long offset;          /@ displacement of file (for archives) @/
X
X   assoc_mem
X   lk_sym_hash(hdrp, syms); /@ Creates lookup-table for symbols @/
X      struct exec *hdrp;    /@ pointer to previously initialized header @/
X      struct nlist *syms;   /@ pointer to previously initialized symbols @/
X
X   func_ptr
X   lk_dynaload(codep, hdrp, hash_table, filename) /@ loads named file @/
X      int* codep;           /@ pointer to memory for return-code @/
X      struct exec* hdrp;    /@ pointer to previously initialized header @/
X      assoc_mem hash_table; /@ previously initialized lookup-table @/
X      char* filename;
X
X   func_ptr  /@ loads a file, given by file-descriptor and offset. @/
X   lk_dynaload_fd(codep, hdrp, hash_tab, fd, offset)
X     int *codep;            /@ pointer to memory for return-code @/
X     struct exec *hdrp;     /@ pointer to previously initialized header @/
X     assoc_mem hash_tab;    /@ previously initialized lookup-table @/
X     int fd;                /@ an open file-descriptor @/
X     long disp;             /@ displacement of file (for archives) @/
X
X   This library furnishes routines for doing a dynamic load of an executable
X   segment ( .o file).
X
X   The caller first must build a lookup-table for the symbols
X   of the executing program.  (See assoc.doc for description
X   of lookup-table routines.)
X
X   Once the lookup-table has been made, the program may repeatedly call
X   lk_dynaload() or lk_dynaload_fd() to load segments.
X   Loaded segments may be freed using free().
X
X   The routines to be used for building the lookup-table are
X   lk_get_header(), lk_get_symbols(), and lk_sym_hash().  These are
X   also potentially useful for other link-editor applications, and
X   for that reason are parameterized so that they may be used on
X   archive members, as well as on individual a.out files.
X
X   lk_get_header() returns 0 on success, -1 on failure.  Sets errno.
X
X   lk_get_symbols() returns a buffer from malloc() on success, null
X     on failure.  Sets errno.
X
X   lk_sym_hash() returns an assoc_mem on success (see assoc.doc), null
X     on failure.  Sets errno.
X
X   lk_dynaload() and lk_dynaload_fd() return a pointer to the entry-point
X     of the .o file on success, null on failure.  Sets *codep (see
X     parameters).  The values for *codep are defined in dyna_link.h:
X
X      #define lk_ok 0
X      #define lk_undefd 1
X      #define lk_bad_format 2
X      #define lk_perror -1
X
X   lk_ok means "okay."
X   lk_undefd means that one or more symbols required by the .o file
X     are not defined in the lookup-table.  In this case the char
X     lk_undefined will have been set to point to a vector containing
X     the undefined symbols.
X   lk_bad_format means that the .o file is not formatted occording
X     to the a.out file conventions.
X   lk_perror means that errno has been set.
X
X
X   Tutorial example:
X
X   main(argc, argv)
X     char argv;
X   {
X     char* me = (char*) (argv[0]);
X     char* prog = (char*)(argv[1]);
X     func_ptr entry_point;
X     assoc_mem hash_tab;
X     struct exec main_hdr;
X     struct nlist * main_syms;
X     int code;
X     int fd = open( me, O_RDONLY );
X
X     lk_get_header(fd, &main_hdr, 0 );
X     main_syms = lk_get_symbols(fd, &main_hdr, 0 );
X     close(fd);
X     hash_tab = lk_sym_hash(&main_hdr, main_syms);
X
X     (func_ptr) entry_point
X          = lk_dynaload( &code, &main_hdr, hash_tab, prog );
X     if(entry_point)
X       (*(func_ptr) entry_point)();
X     else
X        switch(code)
X           {
X           case lk_undefd:
X             { char undef = lk_undefined;
X           printf("undefined:\n");
X           while(*undef) printf("%s\n", *undef++);
X             }
X             break;
X           case lk_perror:
X             perror(prog);
X             break;
X           case lk_bad_format:
X             printf("bad format\n");
X             break;
X           }
X         }
X     }
X     exit(0);
X   }
X
X*/
END_OF_dyna_link.doc
if test 4389 -ne `wc -c <dyna_link.doc`; then
    echo shar: \"dyna_link.doc\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f dyna_link.h -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"dyna_link.h\"
else
echo shar: Extracting \"dyna_link.h\" \(276 characters\)
sed "s/^X//" >dyna_link.h <<'END_OF_dyna_link.h'
X
Xtypedef int ((*func_ptr)());
X
X#define lk_undefd 1
X#define lk_bad_format 2
X#define lk_ok 0
X#define lk_perror -1
X
Xextern char** lk_undefined;
X
Xfunc_ptr dynaload();
X
Xassoc_mem
Xlk_sym_hash();
X
Xstruct nlist *
Xlk_get_symbols();
X
Xfunc_ptr
Xlk_dynaload();
X
Xfunc_ptr
Xlk_dynaload_fd();
END_OF_dyna_link.h
if test 276 -ne `wc -c <dyna_link.h`; then
    echo shar: \"dyna_link.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f assoc.c -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"assoc.c\"
else
echo shar: Extracting \"assoc.c\" \(17401 characters\)
sed "s/^X//" >assoc.c <<'END_OF_assoc.c'
X#include <ctype.h>
X#include <stdio.h>
X
X
X#define PANIC_FILE stderr
X
X#include "assoc.h"
X
Xint* H_getmem();
Xint* assoc_lookup();
X
X
X#define LOWER(ch) (isupper(ch)? tolower(ch) : (ch))
X
X/************************************************************************\
X**************************************************************************
X**                                    **
X**  This package uses hash tables to implement an associative memory,    **
X**  or "name table".  See also "assoc.h" and "assoc_internals.h".    **
X**                                    **
X**  The user may associate names, also called "index strings" with    **
X**  packets of memory, called "mem_cell"s, which come in fixed sizes.    **
X**  Then if you know the name, you can look up the mem_cell or vice    **
X**  versa.                                **
X**                                    **
X**  The collision recovery mechanism is a nifty little scheme           **
X**  of my own invention, which I call "linear-congruential rehash",    **
X**  which means "add one and multiply by three".            **
X**                                    **
X**  The orbit of the rehash function touches exactly half the entries    **
X**  in the table, and the table is never allowed to be over half full,  **
X**  so there will always be an empty slot for a new entry.        **
X**  Removing entries is a little bit tricky. Since the lookup mechanism **
X**  stops and reports failure when it comes to an empty slot in the     **
X**  rehash orbit for the value searched for, when an entry is removed,    **
X**  the values in the same orbit which are there as a result of a     **
X**  collision must be backed up to fill the evacuated slot.          **
X**  The entry number is also there for removing entries.  It provides a **
X**  reference back to the slot which points to the entry.        **
X**                                                                      **
X**  We assume that our machine uses two's complement arithmetic.    **
X**************************************************************************
X\************************************************************************/
X
X/**************************************************************************
X**
X**  An entry looks like this:
X**
X**
X**  [pointers]      [pointees]
X**
X**          ------------------
X**  mem         -> |  entry number  |  index of entry into hash table.
X**          ------------------
X**  mem_cell ->    |             |
X**  (slot)    |         |
X**        | user's goodies |  of size table->value_size
X**            |         |
X**        ------------------
X**  string   -> |         |
X**        |  index string  |
X**        |         |
X**        |         |
X**        ------------------
X**
X**
X**  See string_from_cell(), cell_from_string(), mem_from_cell(), and
X**  cell_from_mem().. all macros.
X**
X\*************************************************************************/
X
X
X
X
X
X
X
X/* N.B. The routine assoc() depends on the fact that if a table is less
X** than half full, the rehash orbit will always find an empty slot.
X** This rehash will hit exactly half the slots before it repeats, provided
X** that the table length is a power of two.
X*/
X#define REHASH(hash,table) (((hash+1)*3) & table -> mask)
X
X
X
X
X/**** factory-procedure, makes new tables. ****/
X
Xassoc_mem
Xnew_assoc_mem(value_size)
X  int value_size; /* storage size of values to be in assoc mem */
X{
X  register assoc_mem table;
X
X  table = (assoc_mem) H_getmem(sizeof (struct assoc_mem_rec));
X
X  table->value_size = value_size;
X  table->entries = 0;
X  table->size = INIT_TABLE_SIZE;
X  table->size_div_2 = table->size / 2;
X  table->mask = table->size -1;
X  table->array = (hash_table *)H_getmem(table->size * (sizeof (mem_cell)));
X
X  return table;
X}
X
X
X
X/* Associates a name with a new mem_cell, or return pointers to previously
X** associated cell.  Initializes new cells to all zero, so you may determine
X** whether or not a cell is new by smudging a "virgin-bit" when you
X** first obtain a new cell.  If you get a cell from assoc() with a
X** fresh new virgin bit, then the cell must be a new one.
X*/
X
X
Xmem_cell
Xassoc( string, table)
X  register char* string;
X  register assoc_mem table;
X{ /* assoc */
X
X  int length;
X  int hashval;
X
X  register int   rehash;
X  register entry assoc_value;
X
X  /* This is essential.  See assoc_internals.h */
X  if (table->entries >= table->size_div_2 - 1)
X    H_expand_table(table);
X
X  hash(string, table->mask, &length, &hashval);
X  rehash = hashval;
X
X look_at_slot:
X  {  register entry * slot = &((*(table->array))[rehash]);
X
X     assoc_value = *slot;
X
X     if ( (assoc_value) == 0)
X       /* Nothing else has hashed to this slot.
X      We will put our string here. */
X       {
X     *slot =  cell_from_mem(
X            (entry) H_getmem(table->value_size + length + sizeof('\0')
X                     + sizeof(entry*)));
X
X     *(mem_from_cell(*slot)) = rehash;
X     assoc_value = *slot;
X     strcpy(string_from_cell(assoc_value, table), string);
X     table->entries++;
X     return assoc_value;        /* <=========== */
X       }
X
X     if (strcmp( string_from_cell(assoc_value,table), string) != 0)
X       {                /* Oops.. collision. */
X     rehash = REHASH(rehash,table);
X     goto look_at_slot;        /* <=========== */
X       }
X     else return assoc_value;        /* <=========== */
X
X   }
X
X
X
X
X
X}                    /* end assoc */
X
X/* Like assoc, except for non-null-terminated strings */
Xmem_cell
Xassocn( string, length, table)
X  register char* string;
X  register assoc_mem table;
X  register int length;
X{ /* assocn */
X
X  int hashval;
X
X  register int   rehash;
X  register entry assoc_value;
X
X  /* This is essential.  See assoc_internals.h */
X  if (table->entries >= table->size_div_2 - 1)
X    H_expand_table(table);
X
X  hashn(string, table->mask, length, &hashval);
X  rehash = hashval;
X
X look_at_slot:
X  {  register entry * slot = &((*(table->array))[rehash]);
X
X     assoc_value = *slot;
X
X     if ( (assoc_value) == 0)
X       /* Nothing else has hashed to this slot.
X      We will put our string here. */
X       {
X     *slot =  cell_from_mem(
X            (entry) H_getmem(table->value_size + length + sizeof('\0')
X                     + sizeof(entry*)));
X
X     *(mem_from_cell(*slot)) = rehash;
X     assoc_value = *slot;
X     strncpy(string_from_cell(assoc_value, table), string, length);
X     table->entries++;
X     return assoc_value;        /* <=========== */
X       }
X
X     if (lstrncmp( string_from_cell(assoc_value,table), string, length) != 0)
X       {                /* Oops.. collision. */
X     rehash = REHASH(rehash,table);
X     goto look_at_slot;        /* <=========== */
X       }
X     else return assoc_value;        /* <=========== */
X
X   }
X
X
X}                    /* end assocn */
X/* Like assoc, except for non-null-terminated strings, and folds cases. */
Xmem_cell
Xassocnf( string, length, table)
X  register char* string;
X  register assoc_mem table;
X  register int length;
X{ /* assocn */
X
X  int hashval;
X
X  register int   rehash;
X  register entry assoc_value;
X
X  /* This is essential.  See assoc_internals.h */
X  if (table->entries >= table->size_div_2 - 1)
X    H_expand_table(table);
X
X  hashnf(string, table->mask, length, &hashval);
X  rehash = hashval;
X
X look_at_slot:
X  {  register entry * slot = &((*(table->array))[rehash]);
X
X     assoc_value = *slot;
X
X     if ( (assoc_value) == 0)
X       /* Nothing else has hashed to this slot.
X      We will put our string here. */
X       {
X     *slot =  cell_from_mem(
X            (entry) H_getmem(table->value_size + length + sizeof('\0')
X                     + sizeof(entry*)));
X
X     *(mem_from_cell(*slot)) = rehash;
X     assoc_value = *slot;
X     strncpy(string_from_cell(assoc_value, table), string, length);
X     table->entries++;
X     return assoc_value;        /* <=========== */
X       }
X
X     if (lstrncmpf( string_from_cell(assoc_value,table), string, length) != 0)
X       {                /* Oops.. collision. */
X     rehash = REHASH(rehash,table);
X     goto look_at_slot;        /* <=========== */
X       }
X     else return assoc_value;        /* <=========== */
X
X   }
X
X}                    /* end assocnf */
X
X/* returns 0 iff a null-terminated string and counted string compare */
Xstatic
Xlstrncmp(nullterm, counted, len)
X  char* nullterm;
X  char* counted;
X{
X
X  while( *nullterm && len && *nullterm++ == *counted++)
X    len--;
X  return !(len == 0 && *nullterm == 0);
X}
X
X/* returns 0 iff a null-terminated string and counted string compare */
X/* folds cases */
Xstatic
Xlstrncmpf(nullterm, counted, len)
X  char* nullterm;
X  char* counted;
X{
X
X  while( *nullterm && len && LOWER(*nullterm) == LOWER(*counted))
X    {
X      len--;
X      nullterm++; counted++;
X    }
X  return !(len == 0 && *nullterm == 0);
X}
X
X
X
X/* Look up the mem_cell associated with a given name. */
X/* Returns NULL if not found.                  */
X
Xmem_cell
Xassoc_lookup( string, table)
X  register char* string;
X  register assoc_mem table;
X{
X  register entry retval;
X  int length;
X  int hashval;
X
X  hash(string, table->mask, &length, &hashval);
X
X  { register int  rehash = hashval;
X    register int * assoc_value = 0;
X
X    look_at_slot:
X    {  entry * slot = &((*(table->array))[rehash]);
X
X       assoc_value = *slot;
X
X       if ( (assoc_value) == 0)
X        /* Nothing has hashed to this slot.
X           Lookup has come to a sorry end. */
X        {
X           return assoc_value;  /* <=========== */
X        }
X
X       if (strcmp( string_from_cell(assoc_value,table), string) == 0)
X        /*  An identical string was previously put in this slot.
X        **  We found it!
X        */
X            {
X           return assoc_value;  /* <=========== */
X        }
X
X       /* collision... try next slot in the rehash orbit */
X       rehash = REHASH(rehash,table);
X       goto look_at_slot;        /* <=========== */
X    }
X
X  }
X
X
X} /* end assoc_lookup */
X
X
Xmem_cell
Xassocn_lookup( string, length, table)
X  register char* string;
X  register assoc_mem table;
X{
X  register entry retval;
X  int hashval;
X
X  hashn(string, table->mask, length, &hashval);
X
X  { register int  rehash = hashval;
X    register int * assoc_value = 0;
X
X  look_at_slot:
X    {  entry * slot = &((*(table->array))[rehash]);
X
X       assoc_value = *slot;
X
X       if ( (assoc_value) == 0)
X     /* Nothing has hashed to this slot.
X        Lookup has come to a sorry end. */
X     {
X       return assoc_value;  /* <=========== */
X     }
X
X       if (lstrncmp( string_from_cell(assoc_value,table), string, length) == 0)
X     /*  An identical string was previously put in this slot.
X     **  We found it!
X     */
X     {
X       return assoc_value;  /* <=========== */
X     }
X
X       /* collision... try next slot in the rehash orbit */
X       rehash = REHASH(rehash,table);
X       goto look_at_slot;        /* <=========== */
X
X     }
X
X  }
X
X
X} /* end assocn_lookup */
X
X
Xmem_cell
Xassocnf_lookup( string, length, table)
X  register char* string;
X  register assoc_mem table;
X{
X  register entry retval;
X  int hashval;
X
X  hashnf(string, table->mask, length, &hashval);
X
X  { register int  rehash = hashval;
X    register int * assoc_value = 0;
X
X  look_at_slot:
X    {  entry * slot = &((*(table->array))[rehash]);
X
X       assoc_value = *slot;
X
X       if ( (assoc_value) == 0)
X     /* Nothing has hashed to this slot.
X        Lookup has come to a sorry end. */
X     {
X       return assoc_value;  /* <=========== */
X     }
X
X       if (lstrncmpf( string_from_cell(assoc_value,table), string, length) == 0)
X     /*  An identical string was previously put in this slot.
X     **  We found it!
X     */
X     {
X       return assoc_value;  /* <=========== */
X     }
X
X       /* collision... try next slot in the rehash orbit */
X       rehash = REHASH(rehash,table);
X       goto look_at_slot;        /* <=========== */
X
X     }
X
X  }
X
X
X} /* end assocnf_lookup */
X
X
X
X
X/* This routine hashes a string and counts the number of chars in it.   */
X/* The hash value is a function of the table size.             */
X
Xstatic
Xhash(string, mask, lenp, hashp)
X  char* string;
X  int mask;     /* Is table size minus one. */
X  int *lenp;
X  int *hashp;
X
X{
X  register int len = 0;
X  register int hash = 0;
X  register char* cursor = string;
X
X  len = 0;
X  hash = 0;
X
X  while (*cursor)
X    { len++;
X      hash += ((hash << 1) + *cursor++);
X    }
X  *hashp = hash & mask;
X  *lenp = len;
X
X
X} /* hash */
X
X/* Like hash, except for counted (not null-terminated) strings */
Xstatic
Xhashn(string, mask, len, hashp)
X  char* string;
X  int mask;     /* Is table size minus one. */
X  int len;
X  int *hashp;
X
X{
X  register int hash = 0;
X  register char* cursor = string;
X
X  hash = 0;
X
X  while (len--)
X    {
X      hash += ((hash << 1) + *cursor++);
X    }
X
X  *hashp = hash & mask;
X
X} /* hashn*/
X/* Like hash, except for counted (not null-terminated) strings */
X/* Folds cases. */
Xstatic
Xhashnf(string, mask, len, hashp)
X  char* string;
X  int mask;     /* Is table size minus one. */
X  int len;
X  int *hashp;
X
X{
X  register int hash = 0;
X  register char* cursor = string;
X
X  hash = 0;
X
X  while (len--)
X    {
X      hash += ((hash << 1) + LOWER(*cursor));
X      cursor++;
X    }
X
X  *hashp = hash & mask;
X
X} /* hashn*/
X
X
X
X
X/* "Safe" memory allocation routine... zeros out memory obtained. */
X
Xstatic int*
XH_getmem(size)
X  int size;
X{
X  int * retval = (int*)calloc(size, sizeof(char));
X  if (retval == (int*)0)
X    {
X    fprintf(PANIC_FILE, "RESOURCE FAILURE: Assoc out of memory. (%d)\n",
X        size);
X    exit(1);
X    }
X  else return retval;
X
X}
X
X
X
X
X
X
X/* When a table becomes half full, we double its size.  (The
X** orbit of the rehash function touches exactly half the slots.)
X**
X*/
X
Xstatic
XH_expand_table(table)
X  register assoc_mem table;
X{
X  register hash_table * old_table = table->array;
X  register int old_size = table->size;
X
X  table->size_div_2 = table->size;
X  table->size = table->size * 2;
X  table->mask = table->size -1;
X
X  table->array = (hash_table *)H_getmem(table->size * (sizeof (mem_cell)));
X
X  /* Move the members from the old small table to be new big one. */
X  { register int recno;
X
X    for (recno = 0; recno < old_size; recno++)
X      if ( (*old_table)[recno] != (entry)0)
X        H_reassoc( (*old_table)[recno], table );
X  }
X
X  cfree (old_table);
X}
X
X
X
X
X
X/* This routine is a little like assoc. It is used by expand_table() to
X** put entries which were in table which overflowed into the new larger one.
X** Used by assoc_free() to put entries back into the table which might
X** have originally been bumped down the rehash orbit by the entry being
X** removed.
X*/
X
Xstatic
XH_reassoc( rec, table)
X  register entry rec;
X  register assoc_mem table;
X{
X  register entry retval;
X  register char* string = string_from_cell(rec, table);
X  int length;
X  int hashval;
X
X  hash(string, table->mask, &length, &hashval);
X
X  { register int  rehash = hashval;
X
X    look_at_slot:
X    {  register entry * slot = &((*(table->array))[rehash]);
X
X       if ( (*slot) == 0)
X        {
X          *slot = rec;
X          *(mem_from_cell(*slot)) = rehash;
X
X          return;        /* <========= */
X        }
X
X       rehash = REHASH(rehash,table);
X       goto look_at_slot;      /* <========= */
X    }
X
X  }
X
X
X} /* H_reassoc */
X
X
X
X
X/* This is a sequencer for a table.  You give it a pointer to an
X** integer variable which you have initialized to zero, and it gives
X** you a member of the table and modifies the variable.  Call it
X** again without changing the variable and it gives you the next one, etc...
X**
X**    { int handle = 0;
X**      mem_cell member;
X**
X**      do { member = assoc_seq(table, &handle);
X**           if (member != NULL) process(member);
X**         }
X**      while (member != NULL);
X**    }
X**
X**
X** DO NOT ADD OR DELETE MEMBERS BETWEEN RELATED CALLS TO assoc_seq().
X** To do so will wreak non-determinancy if the assoc() caused the
X** table to expand, or if the assoc_free() caused a member to be
X** moved back up the rehash chain.  You might very easily miss some
X** members.
X**
X*/
X
Xmem_cell
Xassoc_seq(table, num)
X  register assoc_mem table;
X  register int *num;
X{
X  register hash_table * hash_tab = table->array;
X  register int size = table->size;
X
X  /* Standard linear search algorithm looks for next non-empty slot
X  ** at index *num or further down.
X  */
X  for (; (*num) < size; (*num)++)
X    if ( (*hash_tab)[*num] != (entry)0)
X    { mem_cell retval = (*hash_tab)[*num];
X      (*num)++;
X      return retval;
X    }
X
X  return 0;
X
X}
X
X
X
X/*
X** This procedure removes a member from a table.
X*/
X
Xassoc_free(cell, table)
X  mem_cell cell;
X  assoc_mem table;
X{
X  /* Invariant: next_slot_num and next_slot point to entries in the rehash
X  ** orbit of the cell being removed.  They start out pointing to the
X  ** slot of the condemned cell itself:
X  */
X  register next_slot_num = *(mem_from_cell(cell));
X  register entry *next_slot = &((*(table->array))[next_slot_num]);
X
X  /* Remove the condemned cell. */
X  free(mem_from_cell(*next_slot));
X  *next_slot = 0; /* Splat! got it. */
X  table->entries -= 1;
X
X  /* The entry we just removed might have caused some other entries
X  ** to be "bumped down the rehash orbit" when they were installed in
X  ** the table.  If that was the case, they can not now be found unless
X  ** they are moved to their (now) proper position in the table.
X  */
X   while(
X      next_slot_num = REHASH(next_slot_num,table),
X      next_slot = &((*(table->array))[next_slot_num]),
X      (*next_slot != 0)
X    )
X     { entry mover = *next_slot;
X       *next_slot = 0;
X       H_reassoc(mover, table);
X     }
X
X}/* assoc_free */
X
X
X
X/* Deletes a table and returns 0 if the table is empty.
X** Does not delete table, but returns number of entries remaining if
X** table is not empty.
X*/
X
Xint
Xassoc_mem_free(table)
X  assoc_mem table;
X{
X  if (table->entries == 0)
X    {  free(table->array);
X       free(table);
X       return 0;
X    }
X  else return table->entries;
X
X}
X
X/* Deletes all members in a table, then removes the table. */
X
Xassoc_mem_remove(table)
X  assoc_mem table;
X{ register int num = 0;
X  register hash_table * hash_tab = table->array;
X  register int size = table->size;
X
X  for (; (num) < size; (num)++)
X    if ( (*hash_tab)[num] != (entry)0)
X    {
X          free(mem_from_cell((*hash_tab)[num]));
X    }
X
X
X  free(table->array);
X  free(table);
X
X}
END_OF_assoc.c
if test 17401 -ne `wc -c <assoc.c`; then
    echo shar: \"assoc.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f assoc.doc -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"assoc.doc\"
else
echo shar: Extracting \"assoc.doc\" \(3671 characters\)
sed "s/^X//" >assoc.doc <<'END_OF_assoc.doc'
X
X
X
X#include "assoc.h"
X
X
Xassoc_mem
Xnew_assoc_mem( cell_size );
X  int cell_size;
X
Xmem_cell
Xassoc( string, table );
X  char*     string;
X  assoc_mem table;
X
Xmem_cell
Xassocn( string, length, table );
X  char*     string;
X  int         length;
X  assoc_mem table;
X
Xmem_cell
Xassocnf( string, length, table );
X  char*     string;
X  int         length;
X  assoc_mem table;
X
Xmem_cell
Xassoc_lookup( string, table );
X  char* string;
X  assoc_mem table;
X
Xmem_cell
Xassocn_lookup( string, length, table)
X  register char* string;
X  register assoc_mem table;
X
Xchar*
Xstring_from_cell(cell,table)  /* Macro */
X   mem_cell cell;
X   assoc_mem table;
X
Xmem_cell
Xcell_from_string(string, table) /* Macro */
X  char* string;
X  assoc_mem table;
X
Xmem_cell
Xassoc_seq( table, &seq  )
X  assoc_mem table;
X  int seq = 0;
X
X
Xassoc_free( cell, table );
X  mem_cell cell;
X  assoc_mem table;
X
Xint
Xassoc_mem_free( table )
X  assoc_mem table;
X
Xassoc_mem_remove(table)
X  assoc_mem table;
X
X
X
XAn associative memory is identified by a value of type "assoc_mem".  To
Xobtain one, use the procedure new_assoc_mem().
X
XTo obtain a mem_cell associated with a string use the procedure assoc():
XCaveat: Do not call assoc() when you have a sequencer active. (See below.)
Xassocn() is like assoc(), except it uses counted strings as input parameters,
Xrather than null-terminated strings.  assocnf() is like assocn, except
Xthat it maps strings to lower-case for indexing.
X
XSometimes it is desirable to add a new association, if none exists, but
Xto recognize the situation if an association had been made previously.
XTo this purpose, assoc() will return the mem_cell previously associated
Xwith a string if there was one, but will zero out a new mem_cell when
Xit allocates one. Thus one may determine whether or not a mem_cell is
Xa new one by setting a bit in a mem_cell when it is first associtated
Xwith a string.  The demo program demonstrates this technique.
X
XYou may put pointers into the mem_cells.  You can use this technique to
Xassociate strings with LIFO's for example.  By doing so, you may
Xassociate multiple values, perhaps of different sizes, with one string.
X
X
XTo look up a mem_cell previously associated with a string, use the
Xprocedure assoc_lookup().  Also, see cell_from_string() below.
Xassocn_lookup() is like assoc_lookup(), except that its input parameter
Xis a counted string, rather than a null-terminated string.
X
X
X
XTo obtain the string associated with a mem_cell, use the macro
Xstring_from_cell():
X
X
XThe value returned by string_from_cell is a pointer to the string which
Xis internal to the table.  Thus two strings obtained in this manner may
Xbe compared for equality using = rather than strcmp, which of course is
Xmuch slower.   Furthermore, if one has a string obtained from
Xstring_from_cell, one may use the macro cell_from_string() instead of
Xlookup().  cell_from_string() is faster.
X
X
Xassoc_seq() sequences through a table, returning the cells found there in a
Xnon-deterministic order.  If you put cells into the table as you
Xare sequencing through, the sequencer is likely to miss some values,
Xso don't DO that! Set "seq" to zero before the first call, then don't touch
Xit.  The sequencer is finished when it returns NULL;
X
Xassoc_free() removes a memory cell from a table, and frees its memory.
X
Xassoc_mem_free() deallocates the memory associated with an assoc_mem table
Xand returns zero, if the table was empty.  Otherwize it just returns the
Xnumber of entries remaining in the table.
X
X
Xassoc_mem_remove() deletes all members from a table, then removes the table.
X
XCaveat:
XUse only "assoc_free" and "assoc_mem_free" to deallocation cells and tables.
XUsing "free" will crash your program if you are lucky.
END_OF_assoc.doc
if test 3671 -ne `wc -c <assoc.doc`; then
    echo shar: \"assoc.doc\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f assoc_internals.h -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"assoc_internals.h\"
else
echo shar: Extracting \"assoc_internals.h\" \(1498 characters\)
sed "s/^X//" >assoc_internals.h <<'END_OF_assoc_internals.h'
X
X/**********************************************************************\
X**                                      **
X** internal data types... not for use by the mortal man.. subject to  **
X** changes..  information hiding and all that, don't you know.          **
X**                                      **
X\**********************************************************************/
X
Xtypedef int* H_memory_cell;/* pointers to user's memory area. */
X
Xtypedef H_memory_cell entry;
X
Xtypedef entry hash_table[];
X
Xtypedef struct assoc_mem_rec
X    { hash_table *array;
X       int value_size;   /* User defined size of data values; */
X      int size;      /* Number of slots in table.. power of 2 */
X      int size_div_2; /* always = size / 2 */
X      int mask;      /* always = size-1, for calculating (num mod size)*/
X      int entries;    /* number of entries in assoc mem */
X    }
X     * assoc_memory;
X
X
X/* Get unique stored string associated with a memory cell */
X
X#define str_from_cell(cell,table) \
X    ((char*) (((char*) (cell))  + (table)->value_size))
X
X/* Get memory cell associated with a string returned from string_from_cell*/
X
X#define cell_from_str(string,table) \
X    ((int*)  (((char*) (string)) - (table)->value_size))
X
X#define mem_from_cell(cell) ((int*)    ((char*)(cell) - sizeof(entry)))
X#define cell_from_mem(mem)  ((mem_cell)((char*)(mem)  + sizeof(entry)))
X
X#define INIT_TABLE_SIZE 8 /* Must be a power of two */
X/*************************************************************************
X*************************************************************************/
X
END_OF_assoc_internals.h
if test 1498 -ne `wc -c <assoc_internals.h`; then
    echo shar: \"assoc_internals.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f assoc.h -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"assoc.h\"
else
echo shar: Extracting \"assoc.h\" \(2429 characters\)
sed "s/^X//" >assoc.h <<'END_OF_assoc.h'
X#ifndef ASSOC_DEFD
X#define ASSOC_DEFD
X
X#include "assoc_internals.h"
X
X
X/***********************************************************************
X**
X**  See documentation in "assoc.c"
X**
X***********************************************************************/
X
X/*****/
X/* A handle on an associative memory */
X#define assoc_mem assoc_memory
X
X/*****/
X/* Raw memory pointers from an associative memory. Do not use free() on
X** them.  See assoc_free(). */
X#define mem_cell H_memory_cell
X
X/*****/
X/***** Get unique stored string associated with a memory cell which
X       was returned by assoc(), assoc_lookup() or assoc_seq(). */
X#define string_from_cell(cell,table)  str_from_cell(cell,table)
X
X
X/*****/
X/***** Get memory cell associated with a string which was returned by
X**     string_from_cell  */
X#define cell_from_string(string,table) cell_from_str(string,table)
X
X
X
X/*****/
X/***** Gets new assoc mem */
Xassoc_mem
Xnew_assoc_mem( /* cell_size */ );
X
X
X
X/*****/
X/***** Associates a new cell with a given string. */
Xmem_cell
Xassoc(/* string, table */);
X
X/* Is like assoc, except uses counted string, rather that null-terminated */
Xmem_cell
Xassocn(/*string, string_length, table */);
X
X/*****/
X/***** Looks for a cell previously associated with a given string */
Xmem_cell
Xassoc_lookup(/* string, table */);
X
X/* Like assoc_lookup, except uses counted string, rather than null-
X** terminated string
X*/
Xmem_cell
Xassocn_lookup(/* string, length, table */);
X
X
X/*****/
X/***** Removes a memory cell from a table */
Xassoc_free(/* cell, table */ );
X
X/*****/
X/* Sequences through a table, returning the cells found there in a
X** non-deterministic order.  If you put cells into the table as you
X** are sequencing through, the sequencer may find the added value or
X** it may not, so you probably do not want to do that.  Set the variable
X** "seq" to zero before the first call, then don't touch it.  The
X** sequencer is finished when it returns NULL;
X*/
Xmem_cell
Xassoc_seq( /* table, &seq */ );
X
X
X/*****/
X/* Deallocates the memory associated with an assoc_mem table and returns zero,
X** if the table was empty.  Otherwize it just returns the number of entries
X** remaining in the table.
X*/
Xint
Xassoc_mem_free( /* table */ );
X
X/*****/
X/***** Empties a table, then removes it. */
Xassoc_mem_remove(/* table */ );
X
X
X
X/*****/
X/***** returns number of entries currently in table */
X#define assoc_num_entries(table) (table->entries)
X
X#endif ASSOC_DEFD
END_OF_assoc.h
if test 2429 -ne `wc -c <assoc.h`; then
    echo shar: \"assoc.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f which.c -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"which.c\"
else
echo shar: Extracting \"which.c\" \(1840 characters\)
sed "s/^X//" >which.c <<'END_OF_which.c'
X#include <sys/param.h>
X#include <sys/stat.h>
X
X
X/* This does the equivalent of /bin/which.  That is, given a filename,
X** it searches directories named in the environment variable PATH, until
X** it finds a file with that filename.
X*/
X#define copy_of(name) ((char*) sprintf(malloc(strlen(name)+1), "%s", name))
X
Xstatic
Xexists(filename)
X  char* filename;
X{
X  struct stat buffer;
X  return(stat(filename, &buffer) != -1);
X
X}
X
X/* The PATH string looks something like this:
X**
X** .:/u/djones/bin:/usr/local/bin:/usr/mega/bin:/u/mega/bin
X**
X**
X** except probably longer.
X*/
X
Xchar*
Xwhich(file)
X  char* file;
X{
X
X  if(*file == '/') return copy_of(file);
X
X  {  char* search = (char*)getenv("PATH");
X
X     if(search == 0)
X       search = ".:~/bin:/usr/mega/bin:/usr/local/bin:/usr/new:/usr/ucb:/usr/bin:/bin:/usr/hosts:/usr/games";
X
X     { register char* ptr = search;
X
X       while(*ptr)
X     { char  name[MAXPATHLEN];
X       register char* next = name;
X
X       /* copy directory name into [name] */
X       while(*ptr && *ptr != ':') *next++ = *ptr++;
X       if(*ptr) ptr++;
X
X       *next++ = '/'; /* separates directory name and filename */
X
X       /* copy filename into [name] */
X       { register char* ptr2 = file;
X         while(*ptr2) *next++ = *ptr2++;
X       }
X
X       *next = '\0';
X
X       { char* afile = (char*)(name);
X         if(exists(afile)) return (afile);
X         free(afile);
X       }
X
X     }
X
X     }
X     return file;
X   }
X}
X
X#undef binwhich
X#ifdef binwhich
Xmain(argc, argv)
X  char** argv;
X{
X
X  argc--; argv++;
X
X  while (argc)
X    { char* path = which(*argv);
X      if(path)
X    {
X      printf("%s\n", path);
X      free(path);
X    }
X      else
X    { char* ptr = search;
X      printf("no %s in ", *argv);
X      while(*ptr)
X        { putchar(*ptr==':' ? ' ' : *ptr);
X          ptr++;
X        }
X      putchar('\n');
X    }
X      argc--; argv++;
X    }
X  exit(0);
X}
X#endif binwhich
END_OF_which.c
if test 1840 -ne `wc -c <which.c`; then
    echo shar: \"which.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f smalloc.c -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"smalloc.c\"
else
echo shar: Extracting \"smalloc.c\" \(261 characters\)
sed "s/^X//" >smalloc.c <<'END_OF_smalloc.c'
Xstatic char error[] = "Out of memory\n";
X
Xint*
Xsmalloc(size) /* "Safe" alloc */
X{  int* retval = (int*)calloc(1,size);
X
X   if (retval == 0)
X    { write(2, error, sizeof(error));
X      exit(-1);
X    }
X   else return retval;
X}
X
X
X
Xsfree(ptr)
X{
X  if (ptr != 0) free(ptr);
X}
END_OF_smalloc.c
if test 261 -ne `wc -c <smalloc.c`; then
    echo shar: \"smalloc.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f argv.c -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"argv.c\"
else
echo shar: Extracting \"argv.c\" \(4590 characters\)
sed "s/^X//" >argv.c <<'END_OF_argv.c'
X#include <ctype.h>
X#include <stdio.h>
X
X/***********************************************************************
X**
X** These routines build argv's.  An "argv" is a null-terminated array
X** of pointers to strings.  Argv's are often declared as char** or
X** char* foo [];
X**
X** char***
X** argv_new()
X**
X**    returns a structure which is a "scaffold" for building up
X**    an argv. At any point, the structure will contain an argv in its
X**    first field.  If it overflows, a new, larger one is substituted,
X**    and the old one discarded.  So don't keep direct references to the argv
X**    unless you are not going to put any more stuff into it.
X**
X**    Say
X**         char*** scaffold = (char***)argv_new();
X**
X**    Then, when the argv is completed, dereference it...
X**
X**         char** complete_argv = *scaffold;
X**
X**    Then free the scaffold if you wish...
X**
X**         cfree(scaffold);
X**
X**    The argv itself is also allocated by calloc, and may be cfree()'d when
X**    it is no longer needed.
X**
X**    argv_new() returns 0 if it runs out of memory.
X**
X**
X** int
X** argv_put(scaffold, arg)
X**    char*** scaffold;
X**    char* arg;
X**
X**    puts an additional arg into an argv, increasing the size
X**    if necessary. Returns 0 on success, -1 if it runs out of memory.
X**
X** char**
X** argv_from_str(str)
X**   char* str
X**
X**    Parses a string and builds an argv from it.  It
X**    recognizes quote-marks and escapes (\).
X**
X**    For example,
X**
X**       foo bar  "foo bar"  '\'foo\''  '"foo"'
X**
X**    gets parsed into
X**
X**       foo
X**       bar
X**       foo bar
X**       'foo'
X**       "foo"
X**       (0)
X**
X**    The argv and its components are all allocated by calloc().
X**    Returns 0 if it runs out of memory.
X**
X**
X************************************************************************/
X
X
X
Xstruct argv_rec
X  { char** value;
X    int size;
X    int place;
X  };
X
X
Xargv_put(argv, str)
X  struct argv_rec * argv;
X  char* str;
X{
X  if (argv->place + 1 == argv->size) /* oops.. overflow. */
X    {
X      char** old_argv = argv->value;
X      int old_size = argv->size;
X
X      argv->size = argv->size *2;
X      argv->value = (char**)calloc(1, argv->size*sizeof(char*));
X      if(argv->value == 0) { return -1; }
X      bcopy(old_argv, argv->value, old_size * sizeof(char*));
X      free(old_argv);
X    }
X
X  argv->value[argv->place] = str;
X  argv->place++;
X
X  return 0;
X
X}
X
X
Xstruct argv_rec *
Xargv_new()
X{
X  struct argv_rec* retval =
X    (struct argv_rec*) calloc(1,sizeof(struct argv_rec));
X  if (retval == 0) return 0;
X
X  retval->value = (char**)calloc(1, 2*sizeof(char*));
X  if(retval->value == 0) { free(retval); return 0; }
X
X  retval->size = 2;
X  retval->place = 0;
X
X  return retval;
X}
X
X
Xstatic char*
Xstrip(strp)
X  char** strp;
X{
X  char* str = strp? *strp: 0;
X  char* buffer;
X  char  quote = 0;
X  char* next_p;
X
X  if(str == 0 || *str == 0) return 0;
X
X  buffer = (char*)malloc(strlen(str)+1);
X  if(buffer == 0) return 0;
X
X  next_p  = buffer;
X
X  while (isspace(*str)) str++;
X
X  if(*str == '\'' || *str == '"' ) quote = *str++;
X
X  while(*str && !(isspace(*str) && !quote) && !(quote && *str == quote))
X    {
X      if(*str == '\\') str++;
X      *next_p++ = *str++;
X    }
X
X  if(*str && (quote && *str == quote) ) str++; /* skip end-quote */
X
X  *next_p = 0;
X  { char* retval = (char*)calloc(1, strlen(buffer) +1 );
X    if (retval) sprintf(retval, "%s", buffer);
X    free(buffer);
X    *strp = str;
X    return retval;
X  }
X}
X
X
Xchar**
Xargv_from_str(str)
X  char* str;
X{
X  struct argv_rec* argv;
X  char* next_arg;
X  extern errno;
X
X  errno = 0;
X
X  argv = argv_new();
X  if(argv == 0) return 0;
X
X  while( (next_arg = strip(&str)) != 0)
X    { argv_put(argv, next_arg);
X    }
X
X  { char** retval = argv->value;
X    free(argv);
X    return retval;
X  }
X
X
X}
X
Xfprintf_argv(fp,argv)
X  FILE * fp;
X  char** argv;
X{
X  if(argv)
X    while(*argv) fprintf(fp, "%s\n", *argv++);
X}
X
Xprintf_argv(argv)
X  char** argv;
X{
X  if(argv)
X    while(*argv) printf("%s\n", *argv++);
X}
X
Xint strcmp();
X
Xstatic
Xalcomp(p,q)
X  char**p;
X  char**q;
X{
X  return strcmp(*p,*q);
X}
X
Xsort_argv(argc, argv)
X  char** argv;
X{
X
X  qsort(argv, argc, sizeof(char*), alcomp );
X
X}
X
X
X#undef testing
X#ifdef testing
X#include <stdio.h>
Xmain(argc, argv)
X  char** argv;
X{
X  char  buf[256];
X  char** argy;
X  int argk = 0;
X  char** aargh;
X  scanf("%[^\n]", buf);
X  argy = argv_from_str(buf);
X
X  aargh = argy;
X
X  while(*argy) { printf("%s\n", *argy++ ); fflush(stdout); }
X  {
X    char** p = aargh;
X    while(*p++) argk++;
X  }
X  sort_argv(argk, aargh);
X  while(*aargh) { printf("%s\n", *aargh++ ); fflush(stdout); }
X}
X#endif testing
END_OF_argv.c
if test 4590 -ne `wc -c <argv.c`; then
    echo shar: \"argv.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of shell archive.
exit 0